package com.lbc.search;

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    //  二分查找： 要求被查数组是有序的  -> 找出一个下标 或 下标集合
    public static void main(String[] args) {
        int [] arr = {1,8,10,89,1000,1000,1000,1234};

        int resIndex = binarySearch(arr, 0, arr.length - 1, 1000);
        System.out.println("resIndex = " + resIndex);

        List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);
        System.out.println("resIndexList = " + resIndexList);

    }

    // 二分查找算法
    /**
     *
     * @param arr    数组
     * @param left   左边的索引
     * @param right  右边的索引
     * @param findVal 要查找的值
     * @return  找到就返回下标，没找到就返回 -1
     */
    public static int binarySearch (int [] arr, int left, int right, int findVal) {
        //  如果 left > right ，说明递归完整个数组了，但是没有找打
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if (findVal > midVal) {  // 向右递归
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {  // 向左递归
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }

    /**
     *   思考：怎样找出全部的被找值的下标
     *   1.找到索引值，先不要马上返回
     *   2.向 mid 的左边查找，把满足要求的元素下标加入到集合 ArrayList 中
     *   3.向 mid 的右边查找，把满足要求的元素下标加入到集合 ArrayList 中
     *   4.返回 ArrayList
     */
    public static ArrayList<Integer> binarySearch2 (int [] arr, int left, int right, int findVal) {
        //  如果 left > right ，说明递归完整个数组了，但是没有找打
        if (left > right) {
            return new ArrayList<Integer>();
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if (findVal > midVal) {  // 向右递归
            return binarySearch2(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {  // 向左递归
            return binarySearch2(arr, left, mid - 1, findVal);
        } else {
            ArrayList<Integer> resIndexList = new ArrayList<Integer>();
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {
                    break;
                }
                resIndexList.add(temp);
                temp--;
            }
            resIndexList.add(mid);
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != findVal) {
                    break;
                }
                resIndexList.add(temp);
                temp++;
            }
            return resIndexList;
        }
    }


}
